The present invention relates to link state routing. More specifically, the present invention relates to resynchonizing link state information using link state packets from neighboring nodes upon reintroducing a node into a network. Still more specifically, the present invention deals with a network node sending a message to a neighboring network node upon reintroducing the node into the network in order to receive link state packets from the neighboring node.
A network graph is used to generate a routing table in a network node. The routing table allows a network node to determine what link an outbound packet should be transmitted on to move the packet closer to its destination. In order to generate a network graph, a network typically receives link state packets from the other nodes in a network. Each of the link state packets associated with a node contains information about the distance, delay, or cost from the node to one or more neighboring nodes. Distance, delay, or cost all refer to some metric associated with the link between nodes. The packet is then transmitted to all of the network nodes in the network. A network node receiving link state packets from the other nodes in a network can apply Dijkstra's algorithm to generate a network graph for building a routing table.
Network topology, however, can change. New nodes may be added to a network, links or other network nodes can go offline, or a network node can be reinitialized or reintroduced into the network. Information about the change in network topology typically is transmitted by the neighboring node or nodes recognizing the change in topology to all the other nodes in the network. The neighboring node transmits the information by generating a new link state packet and flooding the network with the new information. The nodes in the network use the new link state packet to generate a new network graph that accounts for the change in network topology.
However, processing the change in network topology is resource intensive. Not only is substantial bandwidth used for flooding the network with new link state packets, other packets being transmitted in the network are dropped while the network nodes struggle to generate new routing tables consistent with the new network topology. The generation of new routing tables also requires substantial processor and memory resources at each network node. Although the significant use of network resources is necessary in some instances, reintroduction of a network node into a network does not necessarily require the regeneration of network graphs where the absence of the node is short in duration. For example, a network node or a link may be momentarily offline, or the routing control protocol running on a network node may have been restarted. Typical systems would treat any momentarily downed network node as they would treat any other permanently offline node. New link state information would have to be propagated through the network, resulting in extensive commitment of network resources.
Currently available techniques for reintroducing a node into a network have significant disadvantages particularly with respect to the extensive use of networking and processing resources. It is therefore desirable to provide a system for reintroducing a node in a network that exhibits desirable characteristics as well or better than the technologies discussed above.